package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 1/12/21 10:08 AM
 *
 *  https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */
public class 剑指_Offer_51_数组中的逆序对 {


    private int count = 0;

    private int[] tmps;

    public int reversePairs(int[] nums) {

        if (nums == null || nums.length <= 1) {

            return 0;
        }

        tmps = new int[nums.length >> 1];
        divide(nums,0,nums.length);
        return count;
    }

    private void divide(int[] nums,int start,int end) {

        if (end - start <= 1) {

            return;
        }

        // 位运算加括号！！！！！
        int mid = start + ((end - start) >> 1);

        divide(nums,start,mid);
        divide(nums,mid,end);

        // merge数据
        for (int i = start; i < mid; i++) {

            tmps[i-start] = nums[i];
        }

        // 从 tmps 和 [mid,end)拿数据，放到 [start,end)
        int rIndex = mid,lIndex = 0,index = start;
        int sep = mid - start;
        while (lIndex < sep) {

            if (rIndex < end && tmps[lIndex] > nums[rIndex]) {

                this.count += (sep - lIndex);
                nums[index] = nums[rIndex++];
            }else {

                nums[index] = tmps[lIndex++];
            }

            index++;
        }
    }

    public static void main(String[] args) {

        剑指_Offer_51_数组中的逆序对 reversePairs = new 剑指_Offer_51_数组中的逆序对();

        int[] ints = {7,5,6,4};
        System.out.println(reversePairs.reversePairs(ints));
//        System.out.println(Arrays.toString(ints));

    }
}
